package Leetcode.lc042;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

/***
 * 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
 */
public class Sloution {
    /***
     * 单调栈，为什么不用单调队列，我认为单调队列适合最值的情况，而处理不了间隙，栈可以一个一个处理栈间隙
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int res=0;
        //栈结构存放借点结算雨水，单调栈
         Deque<Integer> stack=new LinkedList<>();
         //开始遍历
        for(int i=0;i<height.length;i++){
            //单调栈开始操作容积和更换最小入栈，单调递减
            while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
                //结算雨水，获得左墙值
                int heightMin = height[stack.pop()];
                //检查左墙
                if(stack.isEmpty()){
                    break;
                }
                //计算雨水
                int left = stack.peek();
                int leftHeight = height[left];
                int rightHeight=height[i];
                int h=Math.min(leftHeight,rightHeight)-heightMin; //减去洼地，保证凭证
                res+=(i-left-1)*h;   //举个例子 1  4  实际的底 2 算术来3就得减一
            }
            //入栈
            stack.push(i);
        }
        return res;
    }
}
